/* 
#include <iostream>
using namespace std;

int n;
int W;
int w[100];
int v[100];
int dp[10001][10001];

int main(){
    cin>>W>>n;
    for(int i=1;i<=n;++i){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=W;++j){
            if(j<w[i]){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
            }
        }
    }

    cout<<dp[n][W]<<endl;
    
    return 0;
} 
*/

#include <iostream>
using namespace std;

int n;
int W;
int w[100];
int v[100];
int dp[10001];

int main(){
    cin>>W>>n;
    for(int i=1;i<=n;++i){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;++i){
        for(int j=W;j>=0;--j){
            if(j<w[i]){
                dp[j] = dp[j];
            }
            else{
                dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
            }
        }
    }

    cout<<dp[W]<<endl;
    
    return 0;
}